// https://www.lintcode.com/problem/heapify/description

// - 描述
// 给出一个整数数组，堆化操作就是把它变成一个最小堆数组。

// 对于堆数组A，A[0]是堆的根，并对于每个A[i]，A [i * 2 + 1]是A[i]的左儿子并且A[i * 2 + 2]是A[i]的右儿子。

// - 说明
// 什么是堆？

// 堆是一种数据结构，它通常有三种方法：push， pop 和 top。其中，“push”添加新的元素进入堆，“pop”删除堆中最小/最大元素，“top”返回堆中最小/最大元素。
// 什么是堆化？

// 把一个无序整数数组变成一个堆数组。如果是最小堆，每个元素A[i]，我们将得到A[i * 2 + 1] >= A[i]和A[i * 2 + 2] >= A[i]
// 如果有很多种堆化的结果？

// 返回其中任何一个。
// - 样例
// 给出 [3,2,1,4,5]，返回[1,2,3,4,5] 或者任何一个合法的堆数组

// - 挑战
// O(n)的时间复杂度完成堆化


class Solution {
public:
//     /*
//      * @param A: Given an integer array
//      * @return: nothing
//      */
     
//     // 法一：bottom-up O(n)
//     
//     // 假如有N个节点，那么高度为H=logN，最后一层每个父节点最多只需要下调1次，
//     // 倒数第二层最多只需要下调2次，顶点最多需要下调H - 1次，而最后一层父节点共有2^(H-2)个,
//     // 倒数第二层父节点公有2^(H-3),顶点只有1(2^0)个，所以总共的时间复杂度为
//     // s = 1 * 2^(H-2) + 2 * 2^(H-3) + ... + (H-2) * 2^1 + （H-1) * 2^0
//     // 将H代入交叉相减后s= 2N - 3 - log2(N) ?，近似的时间复杂度就是O(N)。

//     void heapify(vector<int> &A) {
//         for (int i = A.size() / 2; i >= 0; i--)
//         {
//             min_heapify(A, i);
//         }
//     }
//     void min_heapify(vector<int>& A, int num)
//     {
//         int min = num;
//         int l = num * 2 + 1;
//         int r = num * 2 + 2;
//         if (l < A.size() && A[l] < A[min])
//         {
//             min = l;
//         }
//         if (r < A.size() && A[r] < A[min])
//         {
//             min = r;
//         }
//         if (min == num)
//         {
//             return;
//         }
//         swap(A[num], A[min]);
//         min_heapify(A, min);
//     }
// };

// 法二：top-down / insertHeap O(nlogn)
// 自顶向下最下面的要调的次数最多，最后一项（H-1) * 2^(H-1)
    void min_heapify(vector<int> &A, int k)
    {
        while (k != 0)
        {
            int parent = (k - 1) / 2;
            if (A[parent] < A[k])
            {
                break;
            }
            swap(A[parent], A[k]);
            k = parent;
        }
    }
    void heapify(vector<int> &A) {
        for (int i = 0; i < A.size(); i++)
        {
            min_heapify(A, i);
        }
    }
};



// python
// import heapq
// class Solution:
    // # @param A: Given an integer array
    // # @return: void
    // def heapify(self, A):
        // # write your code here
        // heapq.heapify(A)